#ifndef NEWTON_INTERPOLATION_H
#define NEWTON_INTERPOLATION_H

#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;

// 计算牛顿插值多项式的函数，直接返回插值结果
double newtonInterpolation(const vector<double>& nodes, const vector<double>& func_values, double x) {
    size_t n = nodes.size();
    vector<vector<double>> table(n, vector<double>(n, 0.0));  // 创建一个下三角矩阵差商表

    // 构建差商表
    for (size_t i = 0; i < n; i++) {
        table[i][0] = func_values[i];  // 将节点处的函数值存放在差商表的第一列
    }
    for (size_t j = 1; j < n; j++) {
        for (size_t i = j; i < n; i++) {
            table[i][j] = (table[i][j - 1] - table[i - 1][j - 1]) / (nodes[i] - nodes[i - j]);
        }
    }

    // 计算牛顿插值多项式的值
    double result = table[0][0];  // 从差商表的第一个元素开始
    double mult = 1.0;
    for (size_t i = 1; i < n; i++) {
        mult *= (x - nodes[i - 1]);
        result += table[i][i] * mult;
    }
    return result;
}

#endif // NEWTON_INTERPOLATION_H